﻿using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Daybreak.Core.SceneGraph;
using Daybreak.Core.Rendering;
using Daybreak.Core.Geometrics;

namespace Daybreak.Core.Terrains
{
    /// <summary>
    /// Terrain with geomipmapped LOD generation
    /// </summary>
    public sealed class MipMapTerrain : ITerrain
    {
        /// <summary>
        /// LOD enumerates the available level of detail modes. Currently there are two modes supported:
        /// - brute force rendering
        /// - geomipmapping
        /// </summary>
        public enum LodMode
        {
            /// <summary>
            /// Brute forcing
            /// </summary>
            None,
            /// <summary>
            /// Geomipmapping
            /// </summary>
            GeoMipMap
        }

        /// <summary>
        /// Structure for the terrain patch. Every terrain patch has its LOD level, a indice list and a index count
        /// specifying the number of elements to be used from the indice array.
        /// </summary>
        struct Patch
        {
            #region Fields

            /// <summary>
            /// The current LOD level of the terrain patch
            /// </summary>
            public int lodLevel;

            /// <summary>
            /// The index list for the terrain patch, containing
            /// the vertex render order.
            /// </summary>
            public int[] Indices;

            /// <summary>
            /// Holds the number of indices from the s_Indices array that are required to render the patch
            /// </summary>
            public int IndiceCount;

            /// <summary>
            /// Holds the BoundingBox of each terrain patch
            /// </summary>
            public BoundingBox BBox;

            #endregion Fields

            /// <summary>
            /// This method simply adds 3 indices to the current terrain patch indexbuffer
            /// </summary>
            /// <param name="counter">A indice counter</param>
            /// <param name="index">A counter which keeps track of the whole indice count</param>
            /// <param name="i0">The bottom point of the triangle</param>
            /// <param name="i1">The top left point of the triangle</param>
            /// <param name="i2">The top right point of the triangle</param>
            public void AddTriangle(ref int counter, ref int index, int i0, int i1, int i2)
            {
                Indices[counter++] = i2;
                Indices[counter++] = i1;
                Indices[counter++] = i0;
                index += 3;
            }


        }

        #region fields
        /// <summary>
        /// Stores the terrain width
        /// </summary>
        private int _mapWidth;

        /// <summary>
        /// Stores the terrain height
        /// </summary>
        private int _mapHeight;

        /// <summary>
        /// Flag to control the geomipmapping function
        /// </summary>
        private bool geomipmapping = false;

        /// <summary>
        /// The array containing all the terrain patches
        /// </summary>
        private Patch[] Patches;

        /// <summary>
        /// The size of a terrain patch must be (2^n)+1
        /// </summary>
        private int patchSize;

        /// <summary>
        /// Variable to hold the count of terrainpatches horizontaly
        /// </summary>
        private int patchCount;

        /// <summary>
        /// Variable that holds the maximum LOD level
        /// </summary>
        private int maxLOD;

        /// <summary>
        /// Variable containing the old camera position
        /// </summary>
        private Vector3 _lastPosition;
        private Matrix _lastView;

        /// <summary>
        /// The array containing all distances according to each LOD level
        /// i.e distance 1000 from the camera to the center of the patch means patch has LOD level 1
        /// </summary>
        private float[] lodDistances;

        Heightmap _heightMap;

        int vertexCount;
        int indexCount;
        int[] indexData;

        internal VertexBuffer vb;
        internal IndexBuffer ib;
        internal VertexDeclaration decl;

        public Scene.Material Material;

        public bool ShowBBoxes = true;

        #endregion

        #region Bitmask to hold all cases we can encounter during the stitching process
        const int dropLeft = 1;
        const int dropRight = 1 << 1;
        const int dropBottom = 1 << 2;
        const int dropTop = 1 << 3;
        const int dropRightCorner = 1 << 4;
        const int dropTopCorner = 1 << 5; 
        #endregion


        /// <summary>
        /// Create the Terrain from the data passed into the constructor
        /// </summary>
        /// <param name="format">Specifies the file format of the heightmap</param>
        /// <param name="filename">Specifies the file to be loaded</param>
        /// <param name="bpp">Specifies the bits per pixel of the heightmap file</param>
        /// <param name="patchsize">Must be (2^n)+1, i.e 9, 17, 33, etc</param>
        /// <param name="mode">The LOD mode to be used</param>
        public MipMapTerrain(HeightData data, int patchsize, LodMode mode)
        {

            if (!data.Loaded) 
                throw new Exception("Heightmap failed to load!");

            _heightMap = new Heightmap(data.DataArray);


            if (mode == LodMode.GeoMipMap) 
                geomipmapping = true;

            // Initialize our variables
            _mapWidth = data.Width;
            _mapHeight = data.Height;

            _lastPosition = new Vector3(float.MaxValue);

            // Set variables
            patchSize = patchsize;

            patchCount = (_mapWidth - 1) / (patchSize - 1);

            // Calculate MaxLOD
            int divisor = patchSize - 1;

            divisor = 128;


            // Variable to save the maximum LOD level
            maxLOD = 0;
            
            while (divisor > 2)
            {
                // iDivisor / 2
                divisor = divisor >> 1;
                maxLOD++;
            }

            // allocate memory for patches
            Patches = new Patch[patchCount * patchCount];

            // Calculate all LOD distances
            lodDistances = new float[8];

            for (int i = 0; i < 8; i++)
            {
                lodDistances[i] = (patchSize * patchSize) * (i + 1 + i / 2) * (i + 1 + i / 2);
                //lodDistances[i] *= 2;
            }

            // create patch data
            for (int i = 0; i < patchCount; i++)
            {
                for (int j = 0; j < patchCount; j++)
                {
                    // set default LOD and allocate memory
                    Patches[i * patchCount + j].Indices = new int[(patchSize - 1) * (patchSize - 1) * 2 * 3];
                }
            }

            CreateTerrain(_mapWidth, _mapHeight, _mapWidth, _mapHeight);
        }

        /// <summary>
        /// Called by the engine on update
        /// </summary>
        public void Update(Camera camera)
        {
            Vector3 camPos = camera.Position;
            float distance;
            bool rotateOnly = false;

            // Check if the camera did move, otherwise dont calculate anything
            if (_lastView == camera.Frustum.Matrix)
                return;

            _lastView = camera.Frustum.Matrix;

            Vector3.DistanceSquared(ref camPos, ref _lastPosition, out distance);

            if (distance < 0.01f) // not enough movement
                rotateOnly = true;

            // Store camera orientation
            _lastPosition = camPos;

            if (!rotateOnly) // if the camera movement was big enough
                CalculatePatchLod();

            if (geomipmapping)
            {
                // recalculate new index buffers if the camera movement was big enough
                if (!rotateOnly)
                    UpdateIndices();

                indexCount = 0;

                ContainmentType contType = ContainmentType.Contains;

                for (int i = 0; i < Patches.Length; i++)
                {
                    camera.FrustumSphere.Contains(ref Patches[i].BBox, out contType);

                    if (contType != ContainmentType.Disjoint)
                    {
                        for (int j = 0; j < Patches[i].IndiceCount; j++)
                        {
                            indexData[indexCount++] = Patches[i].Indices[j];
                        }
                    }
                }
                Engine.GraphicsDevice.Indices = null;

                if (indexCount > 0)
                    ib.SetData<int>(indexData, 0, indexCount);

            }
        }

        private void CalculatePatchLod()
        {
            float distance;
            Vector3 vCenter;
            float ps = patchSize;
            // Patch width / 2
            float p1 = (patchSize >> 1);

            int index = 0;

            for (int z = 0; z < patchCount; z++)
            {
                for (int x = 0; x < patchCount; x++)
                {
                    // calculate center of patch
                    vCenter.X = x * ps + p1;
                    vCenter.Z = z * ps + p1;
                    vCenter.Y = 0;

                    // Scale and transform us
                    //vCenter.TransformCoordinate(_mapTransform);

                    // calculate distance and LOD level, 
                    // depending on the distance from the terrain patch center to the camera

                    Vector3.DistanceSquared(ref _lastPosition, ref vCenter, out distance);

                    for (int i = maxLOD - 1; i >= 0; i--)
                    {
                        if (distance >= lodDistances[i])
                        {
                            Patches[index].lodLevel = i;
                            break;
                        }
                    }
                    index++;
                }
            }

        }

        private void CalculateBBoxes(VertexPositionNormalTexture[] vertexData)
        {
            // set detail level to max

            for (int i = 0; i < Patches.Length; i++)
            {
                Patches[i].lodLevel = 0;
            }

            UpdateIndices();

            for (int i = 0; i < Patches.Length; i++)
            {
                Vector3 pos = vertexData[Patches[i].Indices[0]].Position;

                Patches[i].BBox = new BoundingBox(pos, pos);

                for (int j = 1; j < Patches[i].IndiceCount; j++)
                {
                    UpdateBBox(ref Patches[i].BBox, ref vertexData[Patches[i].Indices[j]].Position);
                }
            }
        }

        private void UpdateBBox(ref BoundingBox bbox, ref Vector3 vertex)
        {
            if (vertex.X < bbox.Min.X)
                bbox.Min.X = vertex.X;
            if (vertex.X > bbox.Max.X)
                bbox.Max.X = vertex.X;

            if (vertex.Y < bbox.Min.Y)
                bbox.Min.Y = vertex.Y;
            if (vertex.Y > bbox.Max.Y)
                bbox.Max.Y = vertex.Y;

            if (vertex.Z < bbox.Min.Z)
                bbox.Min.Z = vertex.Z;
            if (vertex.Z > bbox.Max.Z)
                bbox.Max.Z = vertex.Z;
        }

        /// <summary>
        /// This method goes through each terrain patch and recalculates its indices according to its LOD level.
        /// Everytime we hit an edge, we look for t-junction splits and solve them through stitching.
        /// </summary>
        private void UpdateIndices()
        {
            int i0, i1, i2, i3, i4, i5; 
            int increment;

            int x = 0, z = 0;

            // update each patch's indices
            for (int i = 0; i < patchCount; i++)
            {
                for (int j = 0; j < patchCount; j++)
                {
                    // patch index
                    int p_index = 0;

                    // holding the number of indices for each iteration
                    int index = 0;

                    // stepping through the indicelist
                    int counter = 0;

                    p_index = i * patchCount + j;
                    // reset values for the next iteration
                    x = 0;
                    z = 0;

                    increment = (1 << Patches[p_index].lodLevel);

                    // loop through indices in current patch  
                    while (z + increment < patchSize)
                    {
                        int drop = 0;

                        // Compute the 4 points of our quad, basic case
                        i0 = CalculateIndex(j, i, p_index, x, z);
                        i1 = CalculateIndex(j, i, p_index, x, z + increment);
                        i2 = CalculateIndex(j, i, p_index, x + increment, z);
                        i3 = CalculateIndex(j, i, p_index, x + increment, z + increment);

                        // Check for the case if we've hit an edge and if so, determine which one it is and update the bitmask
                        if (x == 0 && j != 0 && (Patches[p_index].lodLevel < Patches[i * patchCount + (j - 1)].lodLevel))
                            drop |= dropLeft;
                        else
                            if ((x + increment > patchSize - 2) && (j != patchCount - 1) && (Patches[p_index].lodLevel < Patches[i * patchCount + (j + 1)].lodLevel))
                                drop |= dropRight;

                        if (z == 0 && i != 0 && (Patches[p_index].lodLevel < Patches[(i - 1) * patchCount + j].lodLevel))
                            drop |= dropBottom;
                        else
                            if (((z + 2 * increment) > patchSize - 1) && (i != patchCount - 1) && (Patches[p_index].lodLevel < Patches[(i + 1) * patchCount + j].lodLevel))
                                drop |= dropTop;

                        if ((drop & dropLeft) != 0 || (drop & dropRight) != 0)
                        {
                            if (((z + 3 * increment) > patchSize - 1) && (i != patchCount - 1) && (Patches[p_index].lodLevel < Patches[(i + 1) * patchCount + j].lodLevel))
                                drop |= dropTopCorner;
                        }
                        if ((drop & dropBottom) != 0 || (drop & dropTop) != 0)
                        {
                            // Need to do better right hand checking...
                            if ((x + 2 * increment > patchSize - 2) && (j != patchCount - 1) && (Patches[p_index].lodLevel < Patches[i * patchCount + (j + 1)].lodLevel))
                                drop |= dropRightCorner;
                        }

                        // Basic case, no edge
                        if (drop == 0)
                        {
                            // Get the 4 corners of the current quad (i0=bottom left, i1=top left, i2=bottom right, i3=top right)
                            Patches[p_index].AddTriangle( ref counter, ref index, i0, i1, i2);
                            Patches[p_index].AddTriangle( ref counter, ref index, i1, i3, i2);
                        }
                        else if ((drop & dropLeft) != 0)
                        {
                            if ((z / increment) % 2 == 0)
                            {
                                // Now that we're at the edge, get our points,
                                // Since we're dealing with 
                                i4 = CalculateIndex(j, i, p_index, x, z + increment + increment);
                                i5 = CalculateIndex(j, i, p_index, x + increment, z + increment + increment);

                                Patches[p_index].AddTriangle( ref counter, ref index, i0, i4, i3);

                                if ((drop & dropBottom) == 0)
                                    Patches[p_index].AddTriangle( ref counter, ref index, i0, i3, i2);

                                if ((drop & dropTopCorner) == 0)
                                    Patches[p_index].AddTriangle( ref counter, ref index, i4, i5, i3);
                            }
                        }
                        else if ((drop & dropRight) != 0)
                        {
                            if ((z / increment) % 2 == 0)
                            {
                                // Now that we're at the edge, get our points,
                                // Since we're dealing with 
                                i4 = CalculateIndex(j, i, p_index, x, z + increment + increment);
                                i5 = CalculateIndex(j, i, p_index, x + increment, z + increment + increment);

                                if ((drop & dropBottom) == 0)
                                    Patches[p_index].AddTriangle( ref counter, ref index, i0, i1, i2);

                                if ((drop & dropTopCorner) == 0)
                                    Patches[p_index].AddTriangle( ref counter, ref index, i1, i4, i5);

                                Patches[p_index].AddTriangle( ref counter, ref index, i1, i5, i2);
                            }
                        }
                        /* Don't do else if here! */
                        if ((drop & dropBottom) != 0)
                        {
                            if ((x / increment) % 2 == 0)
                            {
                                i4 = CalculateIndex(j, i, p_index, x + increment + increment, z);
                                i5 = CalculateIndex(j, i, p_index, x + increment + increment, z + increment);

                                if ((drop & dropLeft) == 0)
                                    Patches[p_index].AddTriangle( ref counter, ref index, i0, i1, i3);

                                if ((drop & dropRightCorner) == 0)
                                    Patches[p_index].AddTriangle( ref counter, ref index, i3, i5, i4);

                                Patches[p_index].AddTriangle( ref counter, ref index, i0, i3, i4);
                            }
                        }
                        else if ((drop & dropTop) != 0)
                        {
                            if ((x / increment) % 2 == 0)
                            {
                                i4 = CalculateIndex(j, i, p_index, x + increment + increment, z);
                                i5 = CalculateIndex(j, i, p_index, x + increment + increment, z + increment);

                                if ((drop & dropLeft) == 0)
                                    Patches[p_index].AddTriangle( ref counter, ref index, i0, i1, i2);

                                if ((drop & dropRightCorner) == 0)
                                    Patches[p_index].AddTriangle( ref counter, ref index, i2, i5, i4);

                                Patches[p_index].AddTriangle( ref counter, ref index, i1, i5, i2);
                            }
                        }

                        if (x + increment > patchSize - 2)
                        {
                            x = 0;
                            z += increment;   // move down a row
                        }
                        else
                            x += increment;
                    }
                    // Set the indice count calculated
                    Patches[p_index].IndiceCount = index;
                }
            }
        }

        /// <summary>
        /// This method actually calculates the indices of the terrain patch.
        /// </summary>
        /// <param name="PatchX">The patchs X coordinate in the whole terrain patch grid</param>
        /// <param name="PatchZ">The patchs Z coordinate in the whole terrain patch grid</param>
        /// <param name="PatchIndex">The patch index, calculted from the patchs coords PatchZ*patchCount+PatchX</param>
        /// <param name="X">The X indice position within the terrain Patch</param>
        /// <param name="Z">The Z indice position within the terrain Patch</param>
        private int CalculateIndex(int PatchX, int PatchZ, int PatchIndex, int X, int Z)
        {
            return ((Z + ((patchSize - 1) * PatchZ)) * _mapWidth + (X + ((patchSize - 1) * PatchX)));
        }

        /// <summary>
        /// Creates a textured terrain
        /// </summary>
        /// <param name="width">Width</param>
        /// <param name="height">Height</param>
        /// <param name="numVertexWidth">Number of vertices per width</param>
        /// <param name="numVertexHeight">Number of vertices per height</param>
        private void CreateTerrain(float width, float height, int numVertexWidth, int numVertexHeight)
        {
            // Array to hold the vertex data, 3 points per vertex
            vertexCount = numVertexWidth * numVertexHeight;

            VertexPositionNormalTexture[] vertexData = new VertexPositionNormalTexture[vertexCount];

            // calculate the vertexbuffer size
            vb = new VertexBuffer(Engine.GraphicsDevice, vertexCount * VertexPositionNormalTexture.SizeInBytes, BufferUsage.None);

            // fill the local vertexbuffer with the vertex data from the heightmap
            for (int i = 0; i < numVertexHeight; i++)
            {
                for (int j = 0; j < numVertexWidth; j++)
                {
                    // create a terrain cell with 1.0 square size (x,z)
                    vertexData[(i * numVertexWidth + j)].Position.X = j;
                    vertexData[(i * numVertexHeight + j)].Position.Z = i;

                    float hh = _heightMap.GetHeightAndNormal(j, i, out vertexData[(i * numVertexHeight + j)].Normal);
                    // set the z value (height)
                    vertexData[(i * numVertexHeight + j)].Position.Y = hh;

                }
            }

            int a;
            // used for texture coords
            float tu, tv;

            for (int i = a = 0; i < numVertexHeight; i++)
            {
                tv = ((float)i / (float)numVertexHeight);

                for (int j = 0; j < numVertexWidth; j++)
                {
                    tu = ((float)j / (float)numVertexWidth);

                    vertexData[a].TextureCoordinate.X = tu;
                    vertexData[a].TextureCoordinate.Y = tv;

                    //vertexData[a].Normal = Vector3.Up;

                    a++;
                }
            }

            // Brute force indexing for normal calculations

            // set up the brute force indexbuffer, rendering in full detail
            int NumberOfIndices = (_mapWidth - 1) * (_mapHeight - 1) * 6;
            indexData = new int[NumberOfIndices];

            int counter = 0;

            for (int x = 0; x < _mapHeight - 1; x++)
            {
                for (int y = 0; y < _mapWidth - 1; y++)
                {
                    indexData[counter + 0] = x * _mapHeight + (y + 1);
                    indexData[counter + 1] = (x + 1) * _mapHeight + y;
                    indexData[counter + 2] = x * _mapHeight + y;
                    indexData[counter + 3] = x * _mapHeight + (y + 1);
                    indexData[counter + 4] = (x + 1) * _mapHeight + (y + 1);
                    indexData[counter + 5] = (x + 1) * _mapHeight + y;

                    counter = counter + 6;
                }
            }

            // fill the indexbuffer
            ib = new IndexBuffer(Engine.GraphicsDevice, NumberOfIndices * 4, BufferUsage.WriteOnly, IndexElementSize.ThirtyTwoBits);
            ib.SetData<int>(indexData);
            //}
            //else
            //{
            //    indexData = new int[Patches[0].Indices.Length * Patches.Length];
            //    ib = new DynamicIndexBuffer(Engine.GraphicsDevice, Patches[0].Indices.Length * Patches.Length * 4, BufferUsage.WriteOnly, IndexElementSize.ThirtyTwoBits);
            //}


            CalculateBBoxes(vertexData);
            //CalculateNormals(vertexData, indexData);

            vb.SetData<VertexPositionNormalTexture>(vertexData);

            decl = new VertexDeclaration(Engine.GraphicsDevice, VertexPositionNormalTexture.VertexElements);
        }

        private void CalculateNormals(VertexPositionNormalTexture[] vData, int[] iData)
        {
            Vector3[] fNormals = CalculateFaceNormals(vData, iData);
            int[] tempStorage = new int[iData.Length / 3];

            for (int idx = 0; idx < vData.Length; idx++)
            {
                CalculateVertexNormal(fNormals, vData, iData, tempStorage, idx, out vData[idx].Normal);
            }

        }

        private void CalculateVertexNormal(Vector3[] fNormals, VertexPositionNormalTexture[] vData, int[] iData, int[] tempStorage, int indexOfVertice, out Vector3 normal)
        {
            int len = iData.Length / 3;

            // Store each face which has an intersection with the ixVertice'th vertex
            int nbAdjFaces = 0;

            int faceId = 0;

            for (int ix = 0; ix < len; ix++, faceId++)
            {
                Face face = new Face(iData, faceId);

                if (face.VertexIndexA == indexOfVertice)
                    tempStorage[nbAdjFaces++] = ix;
                else
                    if (face.VertexIndexB == indexOfVertice)
                        tempStorage[nbAdjFaces++] = ix;
                    else
                        if (face.VertexIndexC == indexOfVertice)
                            tempStorage[nbAdjFaces++] = ix;
            }

            // Average all adjacent faces normals to get the vertex normal
            Vector3 pn = Vector3.Zero;

            for (int jx = 0; jx < nbAdjFaces; jx++)
            {
                int ixFace = tempStorage[jx];
                pn.X += fNormals[ixFace].X;
                pn.Y += fNormals[ixFace].Y;
                pn.Z += fNormals[ixFace].Z;
            }

            pn.X /= nbAdjFaces;
            pn.Y /= nbAdjFaces;
            pn.Z /= nbAdjFaces;

            pn.Normalize();

            normal = pn;
        }        

        private Vector3 FindFaceNormal(VertexPositionNormalTexture[] vData, int[] iData, int faceIndex)
        {
            faceIndex *= 3;

            int vecIdx1 = iData[faceIndex];
            int vecIdx2 = iData[faceIndex + 1];
            int vecIdx3 = iData[faceIndex + 2];

            Vector3 vec1 = vData[vecIdx1].Position;
            Vector3 vec2 = vData[vecIdx2].Position;
            Vector3 vec3 = vData[vecIdx3].Position;

            Plane plane = new Plane(vec1, vec2, vec3);

            return plane.Normal;
        }

        private Vector3[] CalculateFaceNormals(VertexPositionNormalTexture[] vData, int[] iData)
        {
            int len = iData.Length / 3;

            Vector3[] result = new Vector3[len];

            for (int idx = 0; idx < len; idx++)
            {
                result[idx] = FindFaceNormal(vData, iData, idx);
            }

            return result;
        }

        #region ITerrain Members


        public void RenderSelf(IRender render)
        {
            if (indexCount == 0)
                return;

            TerrainBatch dip = render.RenderQueue.AllocateSlot<TerrainBatch>();

            dip.Declaration = decl;
            dip.IndexBuffer = ib;
            dip.Material = Material;
            dip.Opacity = 1;
            dip.PrimitiveCount = indexCount / 3;
            dip.PrimitiveType = PrimitiveType.TriangleList;
            dip.VertexBuffer = vb;
            dip.VertexCount = vertexCount;
            dip.WorldTransform = Matrix.Identity;

            if (ShowBBoxes && render.Debug)
            {
                for (int i = 0; i < Patches.Length; i++)
                {
                    BBoxItem bb = render.RenderQueue.AllocateSlot<BBoxItem>();

                    bb.Material = Scene.Material.Debug;
                    bb.BoundingVolume = Patches[i].BBox;

                }
            }

        }

        /// <summary>
        /// Gets / Sets if LOD should be enabled or disabled.
        /// </summary>
        public bool UseLOD
        {
            set { geomipmapping = value; }
            get { return geomipmapping; }
        }

        public int TrinaglesCount
        {
            get { return indexCount / 3; }
        }


        public Heightmap Heightmap
        {
            get { return _heightMap; }
        }

        #endregion

        /// <summary>
        /// describes a Mesh face
        /// </summary>
        private struct Face
        {
            public int VertexIndexA;
            public int VertexIndexB;
            public int VertexIndexC;

            public Face(int[] indices, int index)
            {
                index *= 3;

                VertexIndexA = indices[index];
                VertexIndexB = indices[index + 1];
                VertexIndexC = indices[index + 2];

            }
            public Face(int vertexA, int vertexB, int vertexC)
            {
                VertexIndexA = vertexA;
                VertexIndexB = vertexB;
                VertexIndexC = vertexC;
            }
        }

    }
}
